# -*- coding:utf-8 -*-
__author__ = 'gin.chen'


def cross_driver(n, n_list):
    n_list = sorted(n_list)
    sum_number = 0
    if n <= 3:
        return n_list[n - 1]
    # time = (n - 3) * n_list[1]
    # for i in range(2, n):
    #     time += n_list[i]
    # return time
    else:
        sum1 = n_list[1] + n_list[n - 1]

        sum1 += n_list[1] + n_list[n - 2]

        sum2 = n_list[1] + n_list[2]

        sum2 += n_list[1] + n_list[n - 1]

        sum_number += sum1 if (sum1 < sum2) else sum2

        n -= 2

    return sum_number


if __name__ == '__main__':
    nums = input()
    dic = dict()
    for i in range(0, nums):
        n = input()
        a = raw_input()
        n_list = list(map(int, a.split(" ")))
        dic[n] = n_list
        # print cross_driver(n,n_list)
    for i in dic.keys():
        print cross_driver(i, dic[i])
